package cn.tearcry.jsudoku;
import java.util.*;
public class CreateSudoku {
	private long zr=362436069, wr=521288629; 
	private int[] Rows=new int[325];
	private int[] Cols=new int[730];
	private int[] Ur=new int[730];		
	private int[] Uc=new int[325];
	private int[] V=new int[325];
	private int[] W=new int[325];
	private int[] A=new int[88];
	private int[] P=new int[88];
	private int[] A0=new int[88];
	private int[] C=new int[88];
	private int[] I=new int[88];
	private int[] Two=new int[888];
	private int[][] Row=new int[325][10];
	private int[][] Col=new int[730][5];
	private int b,w,f,s1,m0,c1,c2,r1,l,i1,m1,m2,a,p,i,j,k,r,c,d,n=729,m=324,x,y,s,flag1=0,flag2=0,flag3=0; 
	private int mi1,mi2,q7,part,nt,nodes,seed,solutions,min,samples,sam1,clues; 
	 
	private int solve(){ 
	   for(i=0;i<=n;i++)	Ur[i]=0;
	   for(i=0;i<=m;i++)	Uc[i]=0; 
	   clues=0;		
	   for(i=1;i<=81;i++){ 
			 if(A[i]!=0){
				 clues++;
				 r=i*9-9+A[i]; 
				 for(j=1;j<=Cols[r];j++){
					 d=Col[r][j];
					 if(Uc[d]!=0) return -1;
					 Uc[d]++; 
					 for(k=1;k<=Rows[d];k++){Ur[Row[d][k]]++;}
			}//end for 
		 }//end if
		}//end for
	   for(c=1;c<=m;c++){
		   V[c]=0;
		   for(r=1;r<=Rows[c];r++){
			   if(Ur[Row[c][r]]==0)  V[c]++;
		   }//end for
		}//end for
	   i=clues;
	   m0=0;
	   m1=0;
	   solutions=0;
	   if(i==81)	return 1;
	   for(;;){
	   i++;
	   I[i]=0;
	   min=n+1;
	   if(i>81||m0!=0) flag1=1; 
	   if(flag1==0){
	   if(m1!=0){
		   C[i]=m1;
		   flag2=1;
	   } //end if
	   if(flag2==0){
	   w=0;
	   for(c=1;c<=m;c++){
		   if(Uc[c]==0) {
			   if(V[c]<2){
				   C[i]=c;
				   flag2=1;
				   break;
			   }//end if 
	          if(V[c]<=min){
				  w++;
				  W[w]=c;
			  }//end if 
	          if(V[c]<min){
				  w=1;
				  W[w]=c;
				  min=V[c];
			  }//end if
		   }//end if
	   }//end for
	   }

	   if(flag2==0){
	   do
	   c2=(int)((zr=36969*(zr&65535)+(zr>>16))^(wr=18000*(wr&65535)+(wr>>16)))&Two[w];
	   while (c2>=w);
	   C[i]=W[c2+1]; 
	   }
	   }
	   flag2=0;
	   for(;;){
	   if(flag1==0){
	   c=C[i];
	   I[i]++;
	   }
	   if(I[i]>Rows[c]||flag1==1){
	   flag1=0;
	   i--;
	   c=C[i];
	   r=Row[c][I[i]];
	   if(i!=clues){
	   for(j=1;j<=Cols[r];j++){
		   c1=Col[r][j];
		   Uc[c1]--; 
	       for(k=1;k<=Rows[c1];k++){
			   r1=Row[c1][k];
			   Ur[r1]--; 
	           if(Ur[r1]==0){
				   for(l=1;l<=Cols[r1];l++){
					   c2=Col[r1][l];
					   V[c2]++;
				   }//end for
			   }//end if
		   }//end for
	   }//end for
	   if(i>clues) continue; 
	   }//end if
	   else return solutions;
	   }
	   r=Row[c][I[i]];
	   if(Ur[r]!=0) continue;
	   else break;
	   }
	   m0=0;
	   m1=0; 
	   if(part==0){
		   j=9;
		   k=81;
		   x=(r-1)/k+1;
		   y=((r-1)%k)/j+1;
		   s=(r-1)%j+1;
		   A[x*9-9+y]=s;
		   P[x*9-9+y]=i;
	   }//end if
	   for(j=1;j<=Cols[r];j++){
		   c1=Col[r][j];
		   Uc[c1]++;
	   }//end for
	   for(j=1;j<=Cols[r];j++){
		   c1=Col[r][j]; 
		   for(k=1;k<=Rows[c1];k++){
			   r1=Row[c1][k];
			   Ur[r1]++;
			   if(Ur[r1]==1){ 
				 for(l=1;l<=Cols[r1];l++){
					 c2=Col[r1][l];
					 V[c2]--; 
					 if(Uc[c2]+V[c2]<1) m0=c2;
					 if(Uc[c2]==0 && V[c2]<2) m1=c2;
				 }//end for
			   }//end if
		   }//end for
	   }//end for
	   if(i==81){
		   solutions++;
		   if(solutions>1) return 2;
		   if(part==0) return 1;
	   }//end if
	   } 
	}//solve
	int[][] init(int seed,int samples) {
//		char puzzle[100][82];
		int[][] result=new int[9][9];
		zr^=seed;wr+=seed; //zr wr 随机
		for(i=0;i<888;i++) Two[i]=i;//two[i]==i; 
		for(i=1;i<=81;i++) A0[i]=0; //A0[81]==0;
		r=0;
		k=3; 
		for(x=1;x<=9;x++){
			for(y=1;y<=9;y++){
				for(s=1;s<=9;s++){ 
									r++;//r==s+9(y-1)+81(x-1)
									Cols[r]=4;//cols[1]--cols[29]==4								
									Col[r][1]=x*9-9+y; 
									Col[r][2]=(k*((x-1)/k)+(y-1)/3)*9+s+81*1; 
									Col[r][3]=x*9-9+s+81*2; 
									Col[r][4]=y*9-9+s+81*3;
				}//end for
			}//end for
		} //end for
		/*printf("输出Col数组的值");
		for(x=1;x<=729;x++){
			if(x%4==0) printf("\n");
			for(y=1;y<=4;y++)
				printf("%d\t",Col[x][y]);}
		printf("输出Col数组的值完毕\n");*/
		for(c=1;c<=m;c++) Rows[c]=0;//rows[325]==0 
		for(r=1;r<=n;r++){
			for(c=1;c<=Cols[r];c++){ 
									a=Col[r][c];
									Rows[a]++;
									Row[a][Rows[a]]=r;
			} //end for
		}//end for
		sam1=0; 
		for(;;){
		sam1++;
		if(sam1>samples) 
		System.exit(0); 

		for(i=1;i<=81;i++){
		   A[i]=A0[i];//A[81]==0
		   }//end for
		part=0;
		solve(); 

		part++; 
		for(i=1;i<=81;i++){
	    do x=(int)(((zr=36969*(zr&65535)+(zr>>16))^(wr=18000*(wr&65535)+(wr>>16))) >>8)&127;
		while(x>=i);
		x++;
		P[i]=P[x];
		P[x]=i;
		}//end for
		for(i1=1;i1<=81;i1++){
			s1=A[P[i1]];
			if(s1!=0){
				A[P[i1]]=0;
				if(solve()>1) A[P[i1]]=s1;
			}//end if
		}//end for
		//输出
		for(i=1;i<=81;i++) 
		{
			result[(i-1)/9][(i-1)%9]=A[i];
			//System.out.print(A[i]+" ");
			//if(i%9==0) System.out.println("");
		}//end for
		/*System.out.println(""); 
		System.out.println(""); 
		System.out.println(""); 
		System.out.println(""); 
		
		for(i=0;i<9;i++)
		{
			for(int j=0;j<9;j++)
			{
				System.out.print(result[i][j]+" "); 
			}
			System.out.println(""); 
		}*/
		return result;
		}//end for
		
	}

        public int[][] create() {

                Random rand=new Random();
                int a=rand.nextInt(1000000);
                return init(a,1);
        }	
	
}
